package interview;

import java.util.*;

public class lc257 {
      static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
      }

    public static void main(String[] args) {
          TreeNode t = new TreeNode(1);
          t.left = new TreeNode(2);
          t.left.right = new TreeNode(5);
          t.right = new TreeNode(3);
        System.out.println(binaryTreePaths(t));
    }

    /**
     * bfs
     * @param root
     * @return
     */
    public static List<String> binaryTreePaths(TreeNode root) {
        Queue<TreeNode> node = new LinkedList<>();
        Queue<String> queue = new LinkedList<>();
        List<String> ans = new ArrayList<>();
        if(root == null)
            return ans;
        node.offer(root);
        queue.offer(String.valueOf(root.val));
        while(!node.isEmpty()){
            TreeNode node1 = node.poll();
            String s = queue.poll();
            if(node1.left == null && node1.right == null){
                ans.add(s);
            }
            if(node1.left != null){
                node.add(node1.left);
                queue.add(s + "->" + node1.left.val);
            }
            if(node1.right != null){
                node.add(node1.right);
                queue.add(s + "->" + node1.right.val);
            }
        }
        return ans;
    }

    /**
     * dfs
     * @param root
     * @return
     */
    public static List<String> binaryTreePaths2(TreeNode root) {
          List<String> ans = new ArrayList<>();
          List<String> path = new ArrayList<>();
          dfs(root, ans, path);
          return  ans;
    }
    public static void dfs(TreeNode root, List<String> ans,  List<String> path){
          if(root.right == null && root.left == null){
              path.add(root.val + "");
              StringBuilder sb = new StringBuilder();
              for (int i = 0; i < path.size(); i++) {
                  sb.append(path.get(i));
              }
              ans.add(sb.toString());
              return;
          }
          path.add(root.val + "->");
          if(root.left != null){
              dfs(root.left, ans, path);
              path.remove(path.size() - 1);
          }
          if(root.right != null){
              dfs(root.right, ans, path);
              path.remove(path.size() - 1);
          }
    }



    public static List<String> binaryTreePaths3(TreeNode root) {
        List<String> ans = new ArrayList<>();
        String path = "";
        dfs(root, ans, path);
        return  ans;
    }
    public static void dfs(TreeNode root, List<String> ans, String path){
        if(root.right == null && root.left == null){
            path += root.val;
            ans.add(path);
            return;
        }
        path += root.val + "->";
        if(root.left != null){
            dfs(root.left, ans, path);
        }
        if(root.right != null){
            dfs(root.right, ans, path);
        }
    }

}
